Solid-state memory capable of nonvolatile storage of charge, particularly in the form of EEPROM and flash EEPROM packaged as a small form factor card, has recently become the storage of choice in a variety of mobile and handheld devices, notably information appliances and consumer electronics products. Unlike RAM (random access memory) that is also solid-state memory, flash memory is non-volatile, retaining its stored data even after power is turned off. Also, unlike ROM (read only memory), flash memory is rewritable similar to a disk storage device. In spite of the higher cost, flash memory is increasingly being used in mass storage applications. Conventional mass storage, based on rotating magnetic medium such as hard drives and floppy disks, is unsuitable for the mobile and handheld environment. This is because disk drives tend to be bulky, are prone to mechanical failure and have high latency and high power requirements. These undesirable attributes make disk-based storage impractical in most mobile and portable applications. On the other hand, flash memory, whether embedded or in the form of a removable card is ideally suited in the mobile and handheld environment because of its small size, low power consumption, high speed and high reliability features.
Flash EEPROM is similar to EEPROM (electrically erasable and programmable read-only memory) in that it is a non-volatile memory that can be erased and have new data written or “programmed” into their memory cells. Both utilize a floating (unconnected) conductive gate, in a field effect transistor structure, positioned over a channel region in a semiconductor substrate, between source and drain regions. A control gate is then provided over the floating gate. The threshold voltage characteristic of the transistor is controlled by the amount of charge that is retained on the floating gate. That is, for a given level of charge on the floating gate, there is a corresponding voltage (threshold) that must be applied to the control gate before the transistor is turned “on” to permit conduction between its source and drain regions. In particular, flash memory such as Flash EEPROM allows entire blocks of memory cells to be erased at the same time.
The floating gate can hold a range of charges and therefore can be programmed to any threshold voltage level within a threshold voltage window. The size of the threshold voltage window is delimited by the minimum and maximum threshold levels of the device, which in turn correspond to the range of the charges that can be programmed onto the floating gate. The threshold window generally depends on the memory device's characteristics, operating conditions and history. Each distinct, resolvable threshold voltage level range within the window may, in principle, be used to designate a definite memory state of the cell.
The transistor serving as a memory cell is typically programmed from an “erased” state to a “programmed” state by one of two mechanisms. In “hot electron injection,” a high voltage applied to the drain accelerates electrons across the substrate channel region. At the same time a high voltage applied to the control gate pulls the hot electrons through a thin gate dielectric onto the floating gate. In “tunneling injection,” a high voltage is applied to the control gate relative to the substrate. In this way, electrons are pulled from the substrate to the intervening floating gate. While the term “program” has been used historically to describe writing to a memory by injecting electrons to an initially erased charge storage unit of the memory cell so as to alter the memory state, it has now been used interchangeably with more common terms such as “write” or “record.”
The memory device may be erased by a number of mechanisms. For EEPROM, a memory cell is electrically erasable, by applying a high voltage to the substrate relative to the control gate so as to induce electrons in the floating gate to tunnel through a thin oxide to the substrate channel region (i.e., Fowler-Nordheim tunneling.) Typically, the EEPROM is erasable byte by byte. For flash EEPROM, the memory is electrically erasable either all at once or one or more minimum erasable blocks at a time, where a minimum erasable block may consist of one or more sectors and each sector may store 512 bytes or more of data.
The memory device typically comprises one or more memory chips that may be mounted on a card. Each memory chip comprises an array of memory cells supported by peripheral circuits such as decoders and erase, write and read circuits. The more sophisticated memory devices also come with a controller that performs intelligent and higher level memory operations and interfacing.
There are many commercially successful non-volatile solid-state memory devices being used today. These memory devices may be flash EEPROM or may employ other types of nonvolatile memory cells. Examples of flash memory and systems and methods of manufacturing them are given in U.S. Pat. Nos. 5,070,032, 5,095,344, 5,315,541, 5,343,063, and 5,661,053, 5,313,421 and 6,222,762. In particular, flash memory devices with NAND string structures are described in U.S. Pat. Nos. 5,570,315, 5,903,495, 6,046,935. Also nonvolatile memory devices are also manufactured from memory cells with a dielectric layer for storing charge. Instead of the conductive floating gate elements described earlier, a dielectric layer is used. Such memory devices utilizing dielectric storage element have been described by Eitan et al., “NROM: A Novel Localized Trapping, 2-Bit Nonvolatile Memory Cell,” IEEE Electron Device Letters, vol. 21, no. 11, November 2000, pp. 543-545. An oxide-nitride-oxide (“ONO”) dielectric layer extends across the channel between source and drain diffusions. The charge for one data bit is localized in the dielectric layer adjacent to the drain, and the charge for the other data bit is localized in the dielectric layer adjacent to the source. For example, U.S. Pat. Nos. 5,768,192 and 6,011,725 disclose a nonvolatile memory cell having a trapping dielectric sandwiched between two silicon dioxide layers. Multi-state data storage is implemented by separately reading the binary states of the spatially separated charge storage regions within the dielectric.
Read, Write and Erase Performance
In order to improve read and program performance, multiple charge storage elements or memory transistors in an array are read or programmed in parallel. Thus, a “page” of memory elements or cells are read or programmed together. In existing memory architectures, a row typically contains several interleaved pages or it may constitute one page of contiguous memory cells.
In flash memory systems, an erase operation may take as much as an order of magnitude longer than read and program operations. Thus, it is typical to organize the memory cells into blocks, and the memory cells in each block are erased together in a “flash”. Each block typically contains many pages. In this way, the erase time is amortized over a large aggregate of memory cells in a block. In some embodiments, the block of memory cells could be constituted from several memory planes and is more specifically referred to as a “metablock”. For example, a block may have 4 MB memory cells and contain 1K pages if each page has 4 KB memory cells, so a thousand pages are erased together as a unit.
Impact of Block Architecture on Updates and Garbage Collection
The nature of flash memory predicates that a memory cell must always be programmed from the erase state. Unlike magnetic storage or volatile RAM, a previously written location cannot be simply overwritten. The previously written location must first be erased to the erase state before another write can take place. Thus, data are written page by page only to unwritten locations of a block.
If a host writes data of a certain logical address and then updates the data of the logical address again, the updated data cannot overwrite the existing location, but must be written to an erased location. Thus, for the same logical address there are now a current version and an older version. Over several generations of updates, this will result in a number of older versions and a latest updated version of the data among the blocks. When the data with the logical address is read, the latest updated version is accessed; the older versions are treated as obsolete (garbage) data and ignored.
Through use of the memory, obsolete data may accumulate and take up memory space which could otherwise be used for user data. A garbage collection operation is performed to clean out the obsolete data. Since data is stored in blocks, a first block containing a mixture of non-obsolete and obsolete data must first have the non-obsolete data saved by copying to a second block before the first block can be erased. In this way, the obsolete data are “collected” so that the space freed up can be recycled. Garbage collection takes time as it also involves saving non-obsolete data to another block. The time and resource expended are exacerbated if there are more non-obsolete data to copy, which increases with at least two parameters: block size; and the degree of mixing of obsolete and non-obsolete data in each block.
Impact of Block Architecture on Logical to Physical Address Map
Flash memory systems are most commonly provided in the form of a memory card or flash drive that is removably connected with a variety of hosts such as a personal computer, a camera or the like, but may also be embedded within such host systems. A non-volatile memory is typically used by a host to store host data and to retrieve the data at a later time. The host supports applications which can generate and manipulate data files. An operating system in the host provides a data file structure in which a data file is organized into a plurality of logical sectors (typically of 512 bytes). Each logical sector is assigned a logical address, referred to as LBA (“logical block address”) and where the “block” here refers to a block (sector) of data. Thus, the operating system of the host organizes the data from the host-side logical-sector by logical-sector; each logical sector is assigned a unique logical address within a continuous virtual address space of the host. In another embodiment, the unit of address is a cluster of several logical sectors, such as a logical page.
FIG. 1 illustrates schematically the logical address space of a host operating system. Currently, a standard logical addressing scheme is logical block addressing. The host data is parceled out into sectors or blocks of fixed size, typically the size of one sector (512 byte). This LBA “block” is not the same as the erase block of a flash memory. Logical block addressing simply numbers the logical sectors sequentially from 0, 1, 2, 3, . . . . On the other hand, the erase block of the physical memory contains a large number of physical pages, each physical page for storing a logical page of data. Each logical page may be constituted from one or more logical sectors. For example, a logical page, such as logical page 62 of FIG. 2, may contain 4 KB of data corresponding to 8 logical sectors.
When the currently prevalent LBA interface to the memory system is used, files generated by a host to which the memory is connected are assigned unique addresses within the logical address space of the interface. The memory system then commonly maps data between the logical address space and pages of the physical blocks of memory. The memory system keeps track of how the logical address space is mapped into the physical memory but the host has no knowledge of this logical to physical address mapping. On the other hand, the host keeps track of the addresses of its data files within the logical address space but the memory system operates with little or no knowledge of this file system mapping.
In a host write to the non-volatile memory device, the host issues a write command together with a range of logical sector addresses followed by the addressed logical sectors themselves. Similarly, in reading the memory device, the host issues a read command together with a range of logical sector addresses and the device responds by returning the addressed logical sectors to the host. A host write is dependent on the activity of the application generating the data, which is generally unpredictable. However, the host write could be categorized into two main categories: long sequential write; and short random write. The “long” and “short” are relative to the length of a run (sequential addresses) of logical sectors to be written in the context of the physical block size of the memory device.
On the other hand, the memory device has a different organization structure due to the physical characteristics and constraints of the flash memory device. First, a bank of sense amplifiers operating in parallel enables the memory to be read or written page by page (physical page). The page of memory cells could be constituted from several memory planes, each plane with its own set of sense amplifiers and the page is more specifically referred to as a “metapage”. For example, a page may be formed across a row of memory cells in the memory array (which may include several planes) and may have 4 KB cells.
FIG. 2 illustrates a number of logical pages addressable by a host. For example a logical page 62, such as LP0, contains a chunk of 8 logical sectors in sequential order (LBA0, LBA1, . . . , LBA7). For expediency, a logical page is meant to be stored in a physical page of the memory.
When the host writes data to, or reads data from, the memory system, a controller within the memory system translates logical addresses received from the host into physical addresses within the memory array. The logical sectors of data are stored in the corresponding physical addresses in the memory. A logical to physical address table or map or directory is maintained by the controller to keep track of these address translations.
Thus, another issue related to the block architecture is the size of the logical to physical address map. A host writes or read units of data by their logical addresses. An example of a unit of data is a sector of 512 bytes. The flash memory system stores these units of data in some physical locations having their own physical addresses. Typically, data are stored page by page, with each page being one or more sectors. Thus, a map or directory is maintained by the memory system to enable a unit of data of a given logical address to be located physically in the memory.
The logical to physical address map is part of system control and directory data maintained to manage a flash memory system. The directory data is produced and accessed during the course of various memory operations. Thus, its efficient handling and ready access will directly impact performance. This type of system control and directory data is also stored in the flash memory itself since the flash memory is meant for storage and is nonvolatile. However, with an intervening file management system between the controller and the flash memory, the data cannot be accessed as directly and quickly. For example, if the directory data is stored in the flash memory, its access is itself subject to a directory lookup. Also, system control and directory data tends to be active and fragmented, which is not conducive to being stored in a system with a large size block.
Conventionally, this type of control and directory data is cached in the controller RAM, thereby allowing direct and speedy access by the controller. Typically, after the memory device is powered up, a process of initialization enables the flash memory to be scanned in order to compile the necessary system control and directory data to be placed in the controller RAM. This process takes time and requires sufficient controller RAM capacity, all the more so with ever increasing flash memory capacity.
Existing Page-Based Mapping
FIG. 3 illustrates a block partitioned into a plurality of physical pages. In a block 300, each physical page 72 is able to store a logical page 62. For read and write performance, the memory cells in a physical page 72 are read or written in parallel. The block 300 has N physical pages 72 for storing N logical pages 62 of data when each memory cell stores one bit of data. For memory cells that each stores M bits of data, then each physical page 72 will store M logical pages.
U.S. Pat. No. 6,567,307 discloses a method of dealing with sector updates among large erase blocks. Multiple blocks are set up as a scratch pad to store the update data. Garbage collection operations are performed to consolidate the valid sectors among the various blocks and rewrite the sectors into new blocks after rearranging them in logically sequential order. In this way, a block needs not be erased and rewritten at every slightest update. However, the logical to physical mapping is at a fine granularity at the sector or page level, which requires a large storage for such a map. As a copy of the map is preferably maintained in the controller RAM for fast access, a large map requires a large capacity controller RAM, which is expensive. Also, the fine granularity requires frequent updates of the map.
FIG. 4 illustrates an existing page-based block management scheme. Since the memory device writes page by page, the logical to physical map 23 will have to track each page. For example, the first host write, W1, writes logical pages LP0-LP255 into a current open block 20 starting from physical page P0. Each logical page contains one or more sectors addressable by LBAs. The second write, W2, writes an update of the logical page LP1 as logical page LP1′ into physical page P256 which renders obsolete the previously written LP1 at page P1. The third write, W3, writes logical page LP301 into physical page P257. Eventually, when the current open block 20 is filled, it is relegated to a filled block pool 30 while a new current open block is allocated from the free block pool 40. When the free block pool 40 is short of free blocks, it obtains a new one from the filled block pool 30 by a garbage collection operation on a block containing obsolete pages.
Page-based mapping is optimized for a host write pattern in which the writes are mostly short, random writes of a few pages. However, tracking at the page level requires maintenance of a large-size map 23 as each block contains a large number of pages. Referencing the map stored in the flash memory during write and read operations is cumbersome and slow. It is preferable to work with a cached copy of the map in a controller RAM. However, the capacity of the controller RAM is limited and costly, and will be prohibitive to fit the entire map if it is at the page level. Thus, either a large and expensive controller RAM is required to hold the entire map or when the RAM is insufficient to hold the entire map, only a small portion of the map is in RAM and the remaining portion of the map is overlaid in flash memory. In the latter case, read performance is therefore compromised.
In any case, page-based systems tend to have the update data distributed over many blocks and the update data may render many existing blocks partially obsolete. The result often is a large amount of garbage collection necessary for the partially obsolete blocks, which is inefficient and causes premature endurance aging of the memory due to more frequent erase-cycling. Also, there is no systematic and efficient way of dealing with sequential update as compared to non-sequential update.
Existing Group-Based Mapping
One solution to the problem of a large-size map is solved by tracking the logical to physical mapping at a coarser, group-based level. Instead of tracking at the page level, a group of pages is tracked as a unit. The map can therefore be maintained at a logical group level.
FIG. 5 illustrates each block storing a logical group of data. For example, each logical group consists of 1000 logical pages. A logical group 330-0 (LG0) consists of logical pages LP0-LP999 stored in a block 300-0 such as Block0. A logical group 330-1 (LG1) consists of logical pages LP1000-LP1999 stored in another block 300-1 such as Block1. Unlike a logical page which contains one or a few logical units of data, each logical group contains multiple logical pages having a large number of logical units of data (one or two orders of magnitude larger) in sequential logical addresses. The sequential order means the pages within the group are self-indexed. For ease of operation, each logical group has a size that fills a block. Thus, it is sufficient for a group-level map, such as the group-level map 25 of FIG. 6, to track the physical block in which the logical group is in. Once the physical block is located, a given logical address within the logical group can be located by its sequential physical order in the block. In this way, the group-level map 25 has a size that can be substantially reduced. For example, if a logical group contains 1000 logical pages, the map size can be reduced roughly 1000 times compared to that of a page-level map.
In practice, a host does not always write in a large sequential chunk of data that corresponds neatly to a logical group that fills an entire block. Thus, blocks may also need to accommodate non-sequential order of logical pages as well as obsolete pages.
One existing way to avoid mixing of obsolete and non-obsolete pages in a block is to do a read-modify-write (“RMW”). At any time, the sequential order of the pages stored in a block is maintained. For example, a certain logical page in a logical group stored sequentially in a block is being updated. After the entire block of data is read into RAM, the certain logical page is updated in RAM and then the update block of data is rewritten from RAM to a new block. In this way, the logical to physical address mapping within a block is unchanged, only the physical block number need be updated. However, this method of update is inefficient, as it requires an entire block to be rewritten, even if the data to be updated only occupies a small portion of the block. It will also result in a higher frequency of garbage collection among the memory blocks, which is undesirable in view of the limited endurance of this type of memory device.
One solution to avoid RMW in a group-based architecture is to write to a mixture of sequential and non-sequential (chaotic) blocks. Flash memory with a block management system employing a mixture of sequential and chaotic update blocks is disclosed in United States Patent Publication No. US-2005-0144365-A1 dated Jun. 30, 2005, the entire disclosure of which is incorporated herein by reference. The goal is to store the host writes in logical groups consisting of a large number of logical sectors or pages in sequential order in a block. To make garbage collection simple, the logical group size is aligned to an erase block so that each block is filled by one logical group. In this way, the logical to physical map is at the logical group level with a much reduced size of the map and corresponding capacity of the controller RAM.
FIG. 6 illustrates an existing group-based block management scheme. The goal is to store the host writes in logical groups, one logical group per block. Each logical group consists of a large number of logical sectors or logical pages in sequential order. In this way, the logical to physical map is at the logical group level (rather than at the page level), resulting in a much reduced size of the map and corresponding capacity required for the controller RAM. To limit the scope of the logical addresses in a garbage collection, each block is filled by one logical group. For example, the logical group LG0 exactly fills the block 20-1.
As described earlier, the host addresses sectors of data by assigning each with a logical address, LBA. For example, the address space of the host, LBA0, LBA1, LBA2, . . . is partitioned into logical groups each having 1000 LBAs so that LG0 contains LBA0-LBA999, LG1 contains LBA1000 to LBA1999, etc. The sectors of sequential LBAs are packed into logical pages, LP0, LP1, LP2, . . . . In one example, the logical page is the size of one sector. In another example, the logical page is the size of more than one sector. Each logical page is stored in one of physical pages, P0, P1, P2, . . . of the memory. The physical page is a group of memory cells that are operated together in a read or write operation. For example when each logical page is one sector, in a first write, W1, LBA0-LBA999 are written and thus the logical group LG0 is written with logical pages LP0-LP999 respectively filling physical pages P0-P999 of an entire block 20-1.
The host in its various writes can involve LBAs from different logical groups. When a logical group is involved the first time, a “sequential” block dedicated to that logical group such as block 20-1 is opened to store the logical pages in sequential order. In practice, there could be logical pages from multiple logical groups being written concurrently and interleavingly. Thus multiple sequential blocks are opened concurrently to store the logical pages from the respective logical groups.
When a host write is not writing in large segments of logical pages in sequential order, it is written to an update block dedicated to each logical group. The “update” block (also known as a “chaotic” block) is also allocated to each logical group to store the “chaotic” fragmented writes and updates associated with the logical sectors or pages of that logical group. Thus, each active logical group has two blocks allocated to it. A first sequential block for writing sequentially and a second update block for writing chaotically. For example, in a second write, W2, a single LBA is written as LP1′ to update the existing LP1. This update is written to P0 of a dedicated update block 20-2 for the logical group LG0. The previously written LP1 in P1 of sequential block 20-1 is then rendered obsolete. In a third write, W3, another single LBA is written as LP301 to P1 of the update block 20-2.
Eventually, a garbage collection will consolidate the valid logical sectors or pages of that logical group. It will involve copying data between the logical group's pair of sequential and update blocks to end up with a single block. While storing logical group by logical group helps to reduce the size of the map, an additional map is required to track the chaotic update block at the page level. As noted above, for N open logical groups, in addition to N sequential blocks, there will also be N chaotic update blocks to track. Furthermore, as noted, each chaotic or update block must eventually be consolidated by garbage collection logical group by logical group, requiring quite a bit of copying of data between each pair of sequential and update blocks. This scheme requires keeping track of a large number of open blocks and is complicated to manage.
Thus, group based mapping will reduce the logical to physical map size of the sequential blocks but still have to contend with tracking at the page level for every chaotic or update blocks associated with each logical group opened for writes. So while the map size is reduced compared to a purely page-based mapping, it still places a limit on the number of logical groups that can be open simultaneously for writes. In general, group-based mapping is optimized for writes or reads of large chunks of sequential data but suffers from very poor random write performance. Furthermore, a write may be “amplified” by having the same data being copied or re-written multiple times over the course of consolidation and garbage collection, which is inefficient.
Therefore there is a general need for high capacity and high performance non-volatile memory. In particular, there is a need to have a high capacity nonvolatile memory able to conduct memory operations in large blocks without the problems of having to have a large controller RAM to hold a large logical to physical map and without the problem of rewriting data multiple times for consolidation and the need for frequent garbage collections.